int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mlddle = (left + right) / 2;




        if (nums[mlddle] > target)
        {
            right = mlddle - 1;
        }
        else if (nums[mlddle] < target)
        {
            left = mlddle + 1;
        }
        else
        {
            return mlddle;

        }

    }
    return -1;
}
int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;

    for (int fast = 0; fast < numsSize; fast++)
    {
        if (nums[fast] != val)
        {
            nums[slow] = nums[fast];
            slow++;
        }

    }

    return slow;

}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {

    *returnSize = numsSize;

    int* arr = (int*)malloc(*returnSize * sizeof(int));
    if (arr == NULL)
    {
        perror("malloc fail");



    }
    int k = numsSize - 1;
    int i = 0;
    int j = numsSize - 1;
    while (i <= j)
    {
        if (pow(nums[i], 2) > pow(nums[j], 2))
        {
            arr[k] = pow(nums[i], 2);
            i++;
            k--;
        }
        else
        {
            arr[k] = pow(nums[j], 2);
            j--;
            k--;
        }
    }
    return arr;
    free(arr);

}
int minSubArrayLen(int target, int* nums, int numsSize) {
    int i = 0;
    int min = INT_MAX;
    int j = 0;
    int sum = 0;
    for (j = 0; j < numsSize; j++)
    {
        sum += nums[j];
        while (sum >= target)
        {
            int result = j - i + 1;
            if (result < min)
            {
                min = result;
            }
            sum -= nums[i];
            i++;

        }


    }
    return min == INT_MAX ? 0 : min;
}
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    int** ans = (int**)malloc(sizeof(int*) * n);
    int i;
    for (i = 0; i < n; i++)
    {
        ans[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }
    int startx = 0;
    int starty = 0;
    int offset = 1;

    int count = 1;
    int mid = n / 2;
    while (mid)
    {
        int i = startx;
        int j = starty;
        for (j = starty; j < n - offset; j++)
            ans[i][j] = count++;
        for (i = startx; i < n - offset; i++)
            ans[i][j] = count++;
        for (; j > starty; j--)
            ans[i][j] = count++;
        for (; i > startx; i--)
            ans[i][j] = count++;

        mid--;
        startx++;
        starty++;;
        offset += 1;




    }
    if (n % 2)
        ans[n / 2][n / 2] = count;
    return ans;
}
struct ListNode* removeElements(struct ListNode* head, int val) {
    while (head != NULL && head->val == val)
    {
        head = head->next;

    }
    struct ListNode* cur = head;
    while (cur != NULL && cur->next != NULL)
    {
        if (cur->next->val == val)
        {
            cur->next = cur->next->next;
        }
        else
        {
            cur = cur->next;
        }
    }
    return head;

}

struct ListNode* removeElements(struct ListNode* head, int val) {

    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = newnode;
    cur->next = head;
    while (cur->next != NULL)
    {
        if (cur->next->val == val)
            cur->next = cur->next->next;
        else
            cur = cur->next;
    }

    return newnode->next;







}
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3 != NULL)
            n3 = n3->next;








    }
    return n1;










}
struct ListNode* reverse(struct ListNode* prev, struct ListNode* cur)
{
    if (!cur)
        return prev;
    struct ListNode* tmp = cur->next;
    cur->next = prev;

    return reverse(cur, tmp);

}

struct ListNode* reverseList(struct ListNode* head) {
    return reverse(NULL, head);
}
struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (head == NULL)
        return NULL;
    newnode->next = head;
    struct ListNode* cur = newnode;
    while (cur->next != NULL && cur->next->next != NULL)
    {
        struct ListNode* tmp1 = cur->next;
        struct ListNode* tmp2 = cur->next->next->next;
        cur->next = cur->next->next;
        cur->next->next = tmp1;
        tmp1->next = tmp2;
        cur = cur->next->next;
    }
    return newnode->next;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {

    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* fast = newnode;
    struct ListNode* slow = newnode;
    newnode->next = head;
    int k = n + 1;
    while (k)
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;

        k--;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;

    return newnode->next;
}
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;


    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;

        }
    }
    return NULL;
}
